﻿#region Using Statements
using System;
using System.Collections.Generic;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Content.Pipeline;
using Microsoft.Xna.Framework.Content.Pipeline.Graphics;
#endregion

namespace ContentBase.Sprites
{
     ///<summary>
     /// Helper class used for arranging individual sprite images into a single larger texture.
     ///</summary>
    internal static class SpriteSheetPacker
    {
        #region Types

        /// <summary>
        /// Stores sprite data necessary for the arrangement process.
        /// </summary>
        private class SpriteData
        {
            /// <summary>
            /// Gets or sets the index of the sprite in the source sprite list.
            /// </summary>
            public int Index { get; set; }

            /// <summary>
            /// Gets or set the X-axis coordinate of the sprite in the sprite sheet. 
            /// </summary>
            public int X { get; set; }

            /// <summary>
            /// Gets or sets the Y-axis coordinate of the sprite in the sprite sheet. 
            /// </summary>
            public int Y { get; set; }

            /// <summary>
            /// Gets or sets the sprite width.
            /// </summary> 
            public int Width { get; set; }

            /// <summary>
            /// Gets or sets the sprite height.
            /// </summary>
            public int Height { get; set; }

            /// <summary>
            /// Initializes sprite data.
            /// </summary>
            public SpriteData()
            {
                Index = 0;
                X = 0;
                Y = 0;
                Width = 0;
                Height = 0;
            }
        }

        #endregion

        #region Sprite Packaging

        /// <summary>
        /// Packs a list of individual source sprites images into a single larger texture, indicating where each sprite has been placed.
        /// </summary>
        /// <param name="sourceSprites">List of source sprite images.</param>
        /// <param name="spriteRectangles">Rectangles for each sprite in the sprite sheet.</param>
        /// <param name="context">Content processor context.</param>
        /// <returns>Bitmap resource.</returns>
        public static BitmapContent PackSprites(IList<BitmapContent> sourceSprites, ICollection<Rectangle> spriteRectangles, ContentProcessorContext context)
        {
            if (sourceSprites.Count == 0)
                throw new InvalidContentException("No sprites to arrange");

            // store data of all sprites
            List<SpriteData> spriteData = new List<SpriteData>();

            for (int i = 0; i < sourceSprites.Count; i++)
            {
                SpriteData auxSprite = new SpriteData();

                // index of the sprite
                auxSprite.Index = i;

                // sprite dimensions... include single padding pixel around each sprite...
                // ... this avoids filtering problems if the sprite is scaled or rotated...
                auxSprite.Width = sourceSprites[i].Width + 2;
                auxSprite.Height = sourceSprites[i].Height + 2;

                spriteData.Add(auxSprite);
            }

            // sort sprites by size...
            // ... largest sprites first... a sprite is larger if wider
            spriteData.Sort(CompareSpritesBySize);

            // obtain the dimensions of the sprite sheet
            int spriteSheetWidth = 4096;
            int spriteSheetHeight = 0;
            // number of pixels actually used out of the total number of pixels in the sprite sheet
            int totalPixelsUsed = 0;

            for (int i = 0; i < spriteData.Count; i++)
            {
                FindSpritePosition(spriteData, i, spriteSheetWidth);
                spriteSheetHeight = Math.Max(spriteSheetHeight, spriteData[i].Y + spriteData[i].Height);

                totalPixelsUsed += spriteData[i].Width * spriteData[i].Height;
            }

            // logging
            context.Logger.LogImportantMessage("Packet {0} sprites into a {1}x{2} sprite sheet. {3}% efficiency.",
                                               spriteData.Count, spriteSheetWidth, spriteSheetHeight,
                                               totalPixelsUsed * 100 / spriteSheetWidth / spriteSheetHeight);            

            // textures using DXT compressed formats must be multiples of four
            spriteSheetWidth = (spriteSheetWidth + 3) & ~3;
            spriteSheetHeight = (spriteSheetHeight + 3) & ~3;

            // sort back sprites by index order...
            spriteData.Sort(CompareSpritesByIndex);

            // return the sprite sheet
            return CopySpritesToOutput(spriteData, sourceSprites, spriteRectangles, spriteSheetWidth, spriteSheetHeight);
        }

        /// <summary>
        /// Copies the source bitmap data for each individual sprite into the sprite sheet to its chosen position.
        /// </summary>
        /// <param name="spriteData">Data of all the sprites.</param>
        /// <param name="sourceSprites">List of source sprite images.</param>
        /// <param name="spriteRectangles">Rectangles for each sprite in the sprite sheet.</param>
        /// <param name="width">Sprite sheet width.</param>
        /// <param name="height">Sprite sheet height.</param>
        /// <returns>Bitmap resource.</returns>
        private static BitmapContent CopySpritesToOutput(IList<SpriteData> spriteData, IList<BitmapContent> sourceSprites,
                                                         ICollection<Rectangle> spriteRectangles, int width, int height)
        {
            // initialize the sprite sheet
            BitmapContent output = new PixelBitmapContent<Color>(width, height);

            foreach (SpriteData auxSpriteData in spriteData)
            {
                // retrieve the source sprite
                BitmapContent auxSourceSprite = sourceSprites[auxSpriteData.Index];

                // sprite position and dimensions
                int x = auxSpriteData.X;
                int y = auxSpriteData.Y;
                int w = auxSourceSprite.Width;
                int h = auxSourceSprite.Height;

                // copy the source sprite into the sprite sheet
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, 0, w, h), output, new Rectangle(x + 1, y + 1, w, h));

                // generate the padding for every sprite...
                // ... left side...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, 0, 1, h), output, new Rectangle(x, y + 1, 1, h));
                // ... right side...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(w - 1, 0, 1, h), output, new Rectangle(x + w + 1, y + 1, 1, h));
                // ... top side...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, 0, w, 1), output, new Rectangle(x + 1, y, w, 1));
                // ... bottom side...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, h - 1, w, 1), output, new Rectangle(x + 1, y + h + 1, w, 1));
                // ... top-left corner...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, 0, 1, 1), output, new Rectangle(x, y, 1, 1));
                // ... top-right corner...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(w - 1, 0, 1, 1), output, new Rectangle(x + w + 1, y, 1, 1));
                // ... bottom-left corner...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(0, h - 1, 1, 1), output, new Rectangle(x, y + h + 1, 1, 1));
                // ... bottom-right corner...
                BitmapContent.Copy(auxSourceSprite, new Rectangle(w - 1, h - 1, 1, 1), output, new Rectangle(x + w + 1, y + h + 1, 1, 1));

                // remember the rectangle for this sprite
                spriteRectangles.Add(new Rectangle(x + 1, y + 1, w, h));
            }

            return output;
        }

        #endregion

        #region Sprite Arrangement Methods

        /// <summary>
        /// Checks whether a proposed sprite position intersects with any other sprite placed previously in the sprite sheet.
        /// </summary>
        /// <param name="spriteData">Data of all the sprites.</param>
        /// <param name="spriteIndex">Index of the checking sprite.</param>
        /// <param name="x">Proposed sprite position - X</param>
        /// <param name="y">Proposed sprite position - Y</param>
        /// <returns>Index of the intersecting sprite. In case of no intersection, returns -1.</returns>
        private static int FindIntersectingSprite(List<SpriteData> spriteData, int spriteIndex, int x, int y)
        {
            // checking sprite widht and height
            int w = spriteData[spriteIndex].Width;
            int h = spriteData[spriteIndex].Height;

            // check intersection with previously placed sprites
            for (int i = 0; i < spriteIndex; i++)
            {
                // sprite to the right
                if (spriteData[i].X > x + w - 1)
                    continue;

                // sprite to the left
                if (spriteData[i].X + spriteData[i].Width - 1 < x)
                    continue;

                // sprite below
                if (spriteData[i].Y > y + h - 1)
                    continue;

                // sprite above
                if (spriteData[i].Y + spriteData[i].Height - 1 < y)
                    continue;

                // intersection... index of the intersecting sprite
                return i;
            }

            // no intersection
            return -1;
        }

        /// <summary>
        /// Finds the position where the sprite should be placed within the sprite sheet.
        /// </summary>
        /// <param name="spriteData">Data of all the sprites.</param>
        /// <param name="spriteIndex">Index of the checking sprite.</param>
        /// <param name="spriteSheetWidth">Sprite sheet width.</param>
        private static void FindSpritePosition(List<SpriteData> spriteData, int spriteIndex, int spriteSheetWidth)
        {
            // try iteratively several positions... start from the origin
            int x = 0, y = 0;

            while (true)
            {
                // check for intersection
                int intxIndex = FindIntersectingSprite(spriteData, spriteIndex, x, y);

                // no intersection... use that position
                if (intxIndex < 0)
                {
                    spriteData[spriteIndex].X = x;
                    spriteData[spriteIndex].Y = y;
                    return;
                }

                // intersection... go past the existing sprite to the right
                x = spriteData[intxIndex].X + spriteData[intxIndex].Width;
                // if there is no enough space to the right, try the next line instead
                if (x + spriteData[spriteIndex].Width > spriteSheetWidth)
                {
                    x = 0;
                    y++;
                }
            }
        }

        #endregion

        #region Sprite Comparison Methods

        /// <summary>
        /// Comparison function used to sort sprites by size. Sprites will be sorted by decreasing size.
        /// </summary>
        /// <param name="spA">First sprite to compare.</param>
        /// <param name="spB">Second sprite to compare.</param>
        /// <returns>Comparison result.</returns>
        private static int CompareSpritesBySize(SpriteData spA, SpriteData spB)
        {
            // a sprite is larger than other if wider...
            int sizeSpA = spA.Width;
            int sizeSpB = spB.Width;

            return sizeSpB.CompareTo(sizeSpA);
        }

        /// <summary>
        /// Comparison function used to sort sprites by index. Sprites will be sorted by increasing index order.
        /// </summary>
        /// <param name="spA">First sprite to compare.</param>
        /// <param name="spB">Second sprite to compare.</param>
        /// <returns>Comparison result.</returns>
        private static int CompareSpritesByIndex(SpriteData spA, SpriteData spB)
        {
            return spA.Index.CompareTo(spB.Index);
        }

        #endregion 
    }
}
